
package gdatastructure;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import static java.lang.Math.random;
import java.util.LinkedList;
import java.util.ListIterator;
import java.util.Random;

public class Graph{
	private Vertex[] vertexs;//顶点
	private int pos = -1;
	private int size = 0;
	public Steat[] street;
        public int streetsize;
        public car one;
        public car now;
        public int source; //表示需要的车辆数目
        
        //size表示结点个数，link的最大数目为等于size
	Graph(int size){ //构造函数，在表的末尾增加一个Vertex结点
		this.size = size;
		vertexs = new Vertex[size + 1];
		for(int i = 1; i <= size; i++)
			vertexs[i] = new Vertex(new Integer(i));//顶点从1到size
                one=new car();
                now=new car();
	}
        //
        public void showout(){
            System.out.println("one坐标为：("+one.getX()+","+one.getY()+");one所在的街道为："+one.getStreat());
            for(int i=1;i<=streetsize;i++){
                if(street[i].havecar>0){
                    for(int j=0;j<street[i].havecar;j++){
                        System.out.println("车坐标为：("+street[i].n[j].getX()+","+street[i].n[j].getY()+");车所在的街道为："+street[i].n[j].getStreat());
                    }
                }
            }
        }
        //
        public void showvertex(){
            for(int i=1;i<=size;i++){
                System.out.println("路口名称为:"+i+"，路口的坐标为("+vertexs[i].x+","+vertexs[i].y+")");
            }
        }
        //
        public void showstreet(){
            for(int i=1;i<=streetsize;i++){
                System.out.println("第"+i+"条街道名称为:"+i+"，它所连接的起点为："+street[i].from+"，终点为："+street[i].to);
            }
        }
        //
        public void changecar(){
            for(int k=1;k<=streetsize;k++){
                street[k].createcar();
            }
        }
        //
        public void setstreetsize(int a){
            this.streetsize=a;
        }
        //
        public void turnstreet(){ //构建街道 1到j-1 x到j-1
            int size,i,j=1,k=1,x=0;
            double a,b,c;
            VNode temp=null;
            size=this.size;
            int pos;
            street = new Steat[streetsize+1]; //创立一个新的街道
            for(k=1;k<=streetsize;k++)  //街道数组从1开始到streetsize结束
		street[k] = new Steat(2);//顶点从1到size
            for(i=1;i<=size;i++){ //进行作为初始点的数量来循环
                k=0; //再进行一个for循环，循环数量为streetnumber，表示某一个结点上所拥有数量的街道
                ListIterator<VNode> diedai = null;
                //初始结点赋值  问题 数据放不进街道类当中
                diedai = getAllNeighbours2(i).listIterator();//iterator2为minpos所有邻接点迭代器  minpos参数放入结点的下标
                x=j;
		while(diedai.hasNext())
		{
                        
                        street[j].from=i;//初始结点赋值  问题 数据放不进街道类当中
                        temp=diedai.next();//迭代器返回一个vnode为此时道路的终点，将数值读出来
                        street[j].length=temp.linkvalue;
                        street[j].to=temp.index;//将终点下标赋值进去
                        pos=temp.index;
                        street[j].setDomain1(vertexs[i].x);//将起点和终点的横坐标作为街道函数的定义域
                        street[j].setDomain2(vertexs[pos].x);
                        a=vertexs[i].y-vertexs[pos].y;
                        b=vertexs[pos].x -vertexs[i].x;
                        c=vertexs[i].x*vertexs[pos].y-vertexs[pos].x*vertexs[i].y;
                        street[j].setA(a); //将a,b,c的值赋值入相应的steat表中。
                        street[j].setB(b);
                        street[j].setC(c);
                        street[j].index=j;
                        street[j].createcar();//将车放入点中。
                        j=j+1;
                        
 		}
                vertexs[i].streetnumber1=x;
                vertexs[i].streetnumber2=j-1;
            }
        }
       
	public int size(){
		return size;
	}
	public Vertex getVertex(int num){
		return vertexs[num];
	}
	void connect(int from, int to, int linkvalue)
	{
		vertexs[from].link.add(to, linkvalue);
	}
        void turnstreetin(int linkvalue,int x2,int x3){
                vertexs[linkvalue].x=x2;
                vertexs[linkvalue].y=x3;
        }
	void disconnect(int from, int to)
	{
		//单向表
		vertexs[from].link.remove(to);
		//双向表
		//vertexs[from].link.remove(to);
		//vertexs[to].link.remove(from);
	}
	//查询两点之间边的权值,若不存在边，则返回-1表示无穷大
	public double getEdgeValue(int from, int to)
	{
		double value = -1;
		VNode temp = null;
		vertexs[from].link.reset();
//		while((temp = vertexs[from].link.next()) != null)
//		{
//			if(temp.index() == to){
//				value = temp.dc();
//			}
//		}
                return value;
	}
	//返回一个结点的所有邻接点
	public LinkedList<Integer> getAllNeighbours(int index)
	{
		LinkedList<Integer> neighbours  = new LinkedList<Integer>();
		VNode temp = null;
		vertexs[index].link.reset();
		while((temp = vertexs[index].link.next()) != null)
		{
			neighbours.add(temp.index());
		}
		return neighbours;
	}
        	public LinkedList<VNode> getAllNeighbours2(int index)
	{
		LinkedList<VNode> neighbours  = new LinkedList<VNode>();
		VNode temp = null;
		vertexs[index].link.reset();
		while((temp = vertexs[index].link.next()) != null)
		{
			neighbours.add(temp);
		}
		return neighbours;
	}
        public void update(int i){
            VNode temp;
            int cir;
            Random random = new Random();
           if( vertexs[i].link.hasNext())
           {
                cir=random.nextInt()%200;
                   temp=vertexs[i].link.next();
                   temp=temp.next();
                  
           }
        }
        
        //创立函数为初始点
        public void createone(){ //随机一个初始点
            System.out.println("请输入您想要查询车的数量(为0退出查询):");
            Random r=new Random();//136到152为求出一个图上随即的点
            int temp;
            temp=r.nextInt(streetsize);//随即一个街道号
            double a1,b1,c1,domain11,domain21;
            a1=street[temp].getA();
            b1=street[temp].getB();
            c1=street[temp].getC();
            domain11=street[temp].getDomain1();
            domain21=street[temp].getDomain2();
            int la=(int)domain11;
            int lb=(int)domain21;
            double x=0,y;
            if(domain11<domain21) //随机生成车辆的x与y值
                x=domain11+r.nextDouble()+r.nextInt(lb-la);
            if(domain11>domain21)
                x=domain21+r.nextDouble()+r.nextInt(la-lb);
            y=(a1*x+c1)*(-1)/b1;
         
            double tempx1,tempy1,tempx2,tempy2;
            tempx1=domain11;
            tempy1=(a1*tempx1+c1)*(-1)/b1;
            tempx2=domain21;
            tempy2=(a1*tempx2+c1)*(-1)/b1;
            double len1,len2;//将距离起点和末尾点之间的距离求出来，存放进去
            len1=Math.sqrt((x-tempx1)*(x-tempx1)+(y-tempy1)*(y-tempy1));
            len2=Math.sqrt((x-tempx2)*(x-tempx2)+(y-tempy2)*(y-tempy2));            
            one.setX(x);
            one.setY(y);
            one.setStreat(temp);
            one.setTurnfrom(len1);
            one.setTurnto(len2);
        }
        //函数3 得到车辆点后左右找到两个路口,引用函数运算
        public void search(){
            double lenfrom,lento;
            int a,b,c,d;
            lenfrom=one.getTurnfrom();//距离起点的距离拿出来
            lento=one.getTurnto();//距离终点的距离拿出来
            car it1 = new car(0,0,0,0,0);
            car it2 = new car(0,0,0,0,0);
            a=one.getStreat();//得到街道号码
            b=street[a].from;//from路口号
            c=street[a].to;//to路口号
            it1=nextsearch(vertexs[b]);//二次运行的时候在这里已经出现了错误
            it2=nextsearch(vertexs[c]);
            it1.length=it1.length+lenfrom;
            it2.length=it2.length+lento;
            if(it1.length>it2.length){
                now=it2;
            }
            else{
                now=it1;
            }
            it1.length=it1.length-lenfrom;
            it2.length=it2.length-lento;
            //得到最后的now为选中车辆
            //在进行选取多个车辆的时候，使用方法为找到一个，然后将其删除，现在已经找到，进行删除操作
            int m=0;
            m=now.getStreat();//m得到的是选中结点的街道编号
            int i;
            i=now.number;
            street[m].delectcar(i);
            
        }
        
        
        //函数2 在点周围都没有车的情况下，进行向外的延伸 递归函数，运算完成
        public car nextsearch(Vertex index){  //这个函数的问题
            car it = new car(0,0,0,0,0);
            car te = new car(0,0,0,0,0);
            car tem= new car(0,0,0,0,0);
            car first=new car(0,0,0,0,0);
            Vertex[] n;
            n=new Vertex[size+1]; //初始化一个vertex[]的数组
            int j=0;
            /*
            System.out.println("a1");
            it=searchcar(index);//出现问题，
            it.showup();
            System.out.println("a2  ");*/
            now=it;
            double len; int temp;
            ListIterator<VNode> diedai=null;
            
            diedai=getAllNeighbours2(index.value).listIterator();//以该点作为查询点，查询周围的点，在以周围点作为查询点，进行查询
            VNode and=null;
            
            //能否将这里换成street
            int m=index.streetnumber2-index.streetnumber1;
            int y=index.streetnumber1;
            while(m>0){
                and=diedai.next();
                
                len=and.linkvalue; //此时作为外圈距离内圈点的距离
                
                
                temp=and.index;//此时作为外圈的vertex编号
                n[j]=vertexs[temp];  //将这个vertex找到并且拿出来
                j=j+1;
                te=searchcar(vertexs[temp]);//以这个点作为中心点进行向外搜寻
                te.length=te.length+len; //将搜寻到的点加上数值
                if(te.length==0){  //表示没找到
                    // it=te;
                }
                else{
                    if((it.length>te.length&&te.length>0)||it.length==0){ //找到了
                        it=te;
                        now=it;
                    }
                }
                m--;
            }
            /*System.out.println("now");
            now.showup();
            System.out.println("now :");*/
            if(it.length==0){//此时it还是空的，周边还是没有车
                for(int i=0;i<j;i++){
                    first=nextsearch(n[i]);
                    if(it.length==0)
                        it=first;
                    if(it.length>first.length){
                        it=first;
                        now=first;
                    }
                }
                return now;
            }
            else{
                now=it;
                return it;
             }
            
        }
        //更改思路为将车的走向也放入其中
        //函数1 查询一个点周围的其他点的内容 单点周边查询 思路找到一个删除一个  
        public car searchcar(Vertex o){
            car it=new car(0,0,0,0,0);
            double farfrom=-1;
            double temp,temp1;int temp2=0,temp3=1; //temp1为距离，temp2为几号车,temp3为几号街道
            int x=0;
            temp=it.getX();
            VNode l=null;
            Vertex m=o;
            ListIterator<VNode> diedai=null;
            int k=o.value;/*
            diedai=getAllNeighbours2(k).listIterator(); //这里相当于把所有的vnode放出来了，
            while(diedai.hasNext()){ //更改，在这里使用一个迭代器*/
                for(int i=1;i<=streetsize;i++){  
                    if(street[i].to==m.value){//找到o所在的街道 先计算过来的车
                        if(street[i].havecar!=0){
                            x=x+1;
                            for(int j=0;j<street[i].havecar;j++){ //在街道内进行车辆循环
                                temp1=street[i].n[j].getTurnto();
                                street[i].n[j].length=temp1;
                                if(farfrom==-1){
                                    farfrom=temp1;
                                }
                                else{
                                    if(farfrom>temp1&&temp1>0){
                                        farfrom=temp1;
                                        temp2=j;
                                        temp3=i;
                                    }
                                }
                            }
                        }
                    }
                }
                for(int i=vertexs[k].streetnumber1;i<=vertexs[k].streetnumber2;i++){
                        if(street[i].havecar!=0){
                            x=x+1;
                            for(int j=0;j<street[i].havecar;j++){ //在街道内进行车辆循环
                                temp1=street[i].n[j].getTurnto()+street[i].length;
                                street[i].n[j].length=temp1;
                                if(farfrom==-1){
                                    farfrom=temp1;
                                }
                                else{
                                    if(farfrom>temp1&&temp1>0){
                                        farfrom=temp1;
                                        temp2=j;
                                        temp3=i;
                                    }
                                }
                            }
                        }
                }
                /*
                l=diedai.next();
                m=vertexs[l.index];
            }*/
            if(farfrom!=-1)
            {
                now=street[temp3].n[temp2];//找到这个点
                return street[temp3].n[temp2];
            }
            else
            {
                now=it;
                return it;
            }
        }
}

